【题解】 [SHOI2014]概率充电器 概率DP loj2192 | Qiuly's blog!

【题解】 [SHOI2014]概率充电器 概率DP loj2192

Posted on | Edited on | In | Comments:

传送门在这：我是传送门$QwQ$

其实不难发现，我们需要算的就是 $\sum a_i$ (其中 $a_i$ 为点 $i$ 的通电概率) 。我们需要算出每个点的通电概率即可。因为有些点可以自己发电，所以我们要分别考虑父亲和儿子的通电情况。

因为直接设通电概率有些棘手，我们设 $f_i$ 表示点 $i$ 的儿子没有向点 $i$ 通电的概率，这个比较好算，我们顺带算上点 $i$ 自己发电的概率。

枚举每一个儿子，对于这个儿子只有两种情况：该儿子没有通上电，该儿子通上电了且传送失败。两种情况的概率都很好算。我们可以列出转移方程：

其中 $(1-q_u)$ 显然为该点本身不通电的概率，然后枚举儿子 $v$ ，$f_v$ 就是该儿子本来就没有通上电的概率，$(1-f_v)\cdot(1-G_i.p)$ 就是通上电的传送失败(注：$G_i.p$ 是当前连接 $u,v$ 的边的通电概率) 。

那么如何计算父亲传来的电呢？设 $g_i$ 表示点 $i$ 的父亲没有向点 $i$ 通电的概率。计算一下父节点不通电的概率，注意不要计算上该儿子的贡献，不然会乱。计算完不通电的概率后分上面两种情况讨论即可。

两边 $dfs$ 就可以搞定。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=5e5+7;
const int inf=1e9+9;

double ans,f[N],g[N],q[N];
int head[N],cnt,n,tot;
struct Edge{int nxt,to;double p;}G[N<<1];
void add(int x,int y,double p) {G[++cnt]=(Edge){head[x],y,p},head[x]=cnt;}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

void dfs1(int u,int fa) {
    f[u]=1-q[u];
    for(int i=head[u],v;i;i=G[i].nxt) 
        if((v=G[i].to)!=fa)
            dfs1(v,u),f[u]*=(f[v]+(1-f[v])*(1-G[i].p));
}
void dfs2(int u,int fa) {
    for(int i=head[u],v;i;i=G[i].nxt) 
        if((v=G[i].to)!=fa) {
            double res=g[u]*f[u]/(f[v]+(1-f[v])*(1-G[i].p));
            g[v]=res+(1-res)*(1-G[i].p);dfs2(v,u);
        }
}

int main() {
    IN(n);
    for(int i=1;i<n;++i) {
        int x,y,p;IN(x),IN(y),IN(p);
        add(x,y,p/100.0),add(y,x,p/100.0);
    }
    for(int i=1,x;i<=n;++i) IN(x),q[i]=x/100.0;
    dfs1(1,1);
    g[1]=1.0,dfs2(1,1);
    for(int i=1;i<=n;++i) ans+=1-f[i]*g[i];
    printf("%.6f\n",ans);
    return 0;
}

本文标题:【题解】 [SHOI2014]概率充电器 概率DP loj2192

文章作者:Qiuly

发布时间:2019年05月02日 - 00:00

最后更新:2019年05月05日 - 10:07

原始链接:http://qiulyblog.github.io/2019/05/02/[题解]loj2192/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。